3 LEAST UPPER BOUND AND GREATEST LOWER BOUND 23
PROBLEMS

1. Let A be a denumerable subset of R having the following properties: for every
pair of elements x, y of A such that x < y, there are elements u, v, w of A such that
u< x <v<y<w. Show that there is a bijection / of A onto the set Q of rational
numbers, such that x<y implies f(x)<f(y). [Let n->an, n-*bn be bijections
of N onto A and Q. Show by induction on n that there exist finite subsets An <= A,
Bn c Q, and a bijection fn of An onto Bn such that: (1) the at with i^n belong to An;
(2) the bi with / =s£ n belong to Brt; (3) x < y in An implies fn(x) <fn(y); (4) An c An+i
and/, is the restriction of/n+i to An.]

2. Show that the set I of all irrational numbers is equipotent to R (cf. Section 1.9,
Problem 5).

3. LEAST UPPER BOUND AND GREATEST LOWER BOUND

A real number b is said to be a majorant (resp. minorant) of a subset X
of real numbers if x ^ b (resp. b ^ x) for every x e X. A set X c R is said
to be majorized, or bounded from above (resp. minor ized, or bounded from
below) if the set of majorants (resp. minorants) of X is not empty. If X is
majorized, then —X (set of — x, where x eX) is minorized, and for every
majorant b of X, —b is a minorant of —X, and vice versa. A set which
is both majorized and minorized is said to be bounded.

(2.3.1) In order that a set X c= R be bounded, a necessary and sufficient
condition is that there exist an integer n such that \x\ ^ n for every x e X.

For it follows from (III) that if a is a minorant and b a majorant of X,
there exist integers p, q such that — p < a and b < q; take n = p + q. The
converse is obvious.

(2.3.2) If a nonempty subset XofJL is majorized, the set M of majorants
ofX has a smallest element.

Let 0eX, beM; by (III), for every integer n, there is an integer m
such that b ^ a + m • 2~n; on the other hand, if c is a majorant of X, so
is every y^c? so there is a smallest pn such that a 4- pn2~n is a
majorant of X; this implies that, if In = [a + (pn - l)2~rt, a + pn2~n]9
ln n X is not empty. As pn2~n = (2^w)2~n~1, we necessarily have pn+l = 2pn
orpn+l =2pn— 1, since a +(2pn — 2)2~fl~1 is not a majorant; in other words,cts